//split an array into two parts S1 and S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is minimized
//n: the size of the array n < 1000
//the range of elements in the array 0 =< s[i] <= 10^6
#include <iostream>
#include <vector>
#include <deque>
#include <iterator>
#include <algorithm>
#include <numeric>
//method one, reduce it to decision problems such that if there is an subarray s1 , s1.sum = s.sum/2, if not, find s1.sum = s.sum-1;
bool find_subarray(const std::vector<int> &s, int sum, std::deque<int> &s1) {
	// t[k][n] represents if there is a subarray from (0..k) whose sum is n
	std::vector<std::vector<bool> > t(s.size(), std::vector<bool>(sum+1,false) ); 
	// p[k][n] represents if s[k] is selected to form this subarray
	std::vector<std::vector<bool> > p(s.size(), std::vector<bool>(sum+1,false) ); 
	for (int k = 0; k < s.size(); ++k) {
		t[k][0] = true;
	}
	if (s[0] <= sum) {
		t[0][s[0]] = true;
		p[0][s[0]] = true;
	}
	for (int k = 1; k < s.size(); ++k) {
		for (int n = 1; n <= sum; ++n) {
			t[k][n] = t[k-1][n];
			if (s[k] <= n && t[k][n] == false) {
				t[k][n] = t[k][n] || t[k-1][n-s[k]];
				if (t[k][n])
					p[k][n] = true;
			}
		}
	}
	if (t[s.size() - 1][sum] == true)
		for (int k = s.size() - 1, n = sum; k >= 0; --k) {
			if (p[k][n] == true) {
				s1.push_front(s[k]);
				n -= s[k];
			}
		}
	return t[s.size() - 1][sum];
}

void find_optimal_subarray(const std::vector<int> &s) {
	int sum = std::accumulate(s.begin(),s.end(),0);
	sum /= 2;
	std::deque<int> s1;
	while ( !find_subarray(s,sum,s1)){
		--sum;
	}
	std::copy(s1.begin(), s1.end(), std::ostream_iterator<int>(std::cout, " "));
	std::cout << std::endl;
}

void test_find_subarray(){
	int a[] = { 99, 50, 1, 50};
	std::vector<int> s(a, a+ sizeof(a)/sizeof(int) );
	std::deque<int> s1;
	int sum;
	while (std::cin >> sum) {
		s1.resize(0);
		if(find_subarray(s,sum,s1)){
			std::copy(s1.begin(), s1.end(), std::ostream_iterator<int>(std::cout, " "));
			std::cout << std::endl;
		}
		else {
			std::cout << "there is no subarray whose array is " << sum << std::endl;
		}
	}
}



//method two, Time = O(2^n)
//use a binary counter to indicate which element is selected
struct BinaryCounter{
	BinaryCounter(int n) : bcounter(n,false) {  }
	std::vector<bool> bcounter;
	BinaryCounter& operator++();
	BinaryCounter operator++(int);
	bool operator[](int i) { return bcounter[i]; }
	bool is_max();
};

BinaryCounter& BinaryCounter::operator++() {
	bool carry = false;
	for (int i = 0; i < bcounter.size(); ++i) {
		if(bcounter[i] == true)
			bcounter[i] = false;
		else {
			bcounter[i] = true;
			return *this;
		}
	}
	return *this;
}

BinaryCounter BinaryCounter::operator++(int){
	BinaryCounter bc = *this;
	++*this;
	return bc;
}

bool BinaryCounter::is_max() {
	for (int i =0; i < bcounter.size(); ++i)
		if (bcounter[i] == false)
			return false;
	return true;
}

void find_optimal_subarray_exp(const std::vector<int>& s){
	int sum_s = std::accumulate(s.begin(), s.end(), 0);
	sum_s /= 2;
	BinaryCounter bc(s.size());
	std::vector<bool> opt;
	int optimal_diff = sum_s;
	while(!bc.is_max()){
		int sum_s1 = 0;
		for (int i = 0; i < s.size(); ++i) {
			if(bc[i])
				sum_s1 += s[i];
		}
		int diff = std::abs(sum_s1-sum_s);
		if (diff < optimal_diff) {
			optimal_diff = diff;
			opt = bc.bcounter;
		}
		++bc;
	}
	for (int i = 0; i< s.size(); ++i)
		if(opt[i])
			std::cout << s[i] << " ";
	std::cout << std::endl;
}

void test_find_optimal_subarray(){
	int a[] = { 5, 3, 3, 3, 5, 6};
	std::vector<int> s(a, a+ sizeof(a)/sizeof(int) );
	std::cout << " **** Dynamic Programming **** \n";
	find_optimal_subarray(s);
	std::cout << " **** Brute Force **** \n";
	find_optimal_subarray_exp(s);
}
